//There are two sorted arrays A and B of size m and n respectively.Find the median of the two sorted
//arrays.The overall run time complexity should be O(log(m + n)).

#include<iostream>

class Solution
{
public:
	size_t MidoftwoArray(int A[], size_t A_len, int B[], int B_len, int k)
	{
		int A_num = 0;
		int B_num = 0;
		int flag = 0;
		while (k != 0)
		{
			if (k == 1)
			{
				if (A[A_num + k / 2 - 1] < B[B_num + k / 2 - 1])
				{
					printf("k in A array\n");
					return B_num + 1;
				}
				else
				{
					printf("k in B array\n");
					return A_num + 1;
				}

			}
			if (A[A_num + k / 2 - 1] < B[B_num + k / 2 - 1])
			{
				B_num = B_num + k / 2 - 1;
				flag = 1;
			}
			else
			{
				A_num = A_num + k / 2 - 1;
				flag = 2;
			}
			k = k - k / 2;
		}
		if (flag == 1)
		{
			return A_num;
		}
		else{
			return A_num;
		}
	}
};

int main()
{
	int a[] = { 1, 4, 6, 8, 10 };
	int b[] = { 2, 3, 4, 11, 15 };
	int k = 8;
	Solution s;
	std::cout << s.MidoftwoArray(a, 5, b, 5, k) << std::endl;
	return 0;
}